package problem70_Climbing_Stairs;

/**
 * 题目提示动态规划。我们知道第 n 阶只与第 n - 1 阶和 第 n - 2 阶有关，
 * 关系为ways[n] = ways[n - 1] + ways[n - 2]，存储的时候只需要2个存储单元，本题用ways[0]存 n - 2 阶的走法数，ways[1]存储 n - 1 阶走法数：
 * @author Ivan
 *
 */
public class Solution {
	public int climbStairs(int n) {
		int[] ways={1,2};
		if(n<3) return ways[n-1];
		for(int i=3;i<=n;i++){
			int tmp=ways[1];
			ways[1]+=ways[0];
			ways[0]=tmp;
		}
		return ways[1];
	}
	public static void main(String[] args){
		System.out.println(new Solution().climbStairs(30));
	}
}
